package array

//给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
//candidates 中的每个数字在每个组合中只能使用 一次 。
//
//注意：解集不能包含重复的组合。
//
//
//
//示例 1:
//
//输入: candidates = [10,1,2,7,6,1,5], target = 8,
//输出:
//[
//[1,1,6],
//[1,2,5],
//[1,7],
//[2,6]
//]
import (
	"sort"
)

var ans [][]int
var path []int
var candidates []int

func dfs(start int, target int) {
	if target == 0 {
		ans = append(ans, path)
		return
	}
	for i := start; i < len(candidates) && target-candidates[i] >= 0; i++ {
		if i > start && candidates[i] == candidates[i-1] {
			continue
		}
		path = append(path, candidates[i])
		dfs(i+1, target-candidates[i])
		path = path[:len(path)-1]
	}
}

func combinationSum2(candi []int, target int) [][]int {
	sort.Ints(candi)
	candidates = candi
	dfs(0, target)
	return ans
}
